package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//15. 三数之和
//
//给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
//
//注意：答案中不可以包含重复的三元组。
//
//例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]


public class Solution015 {
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		if (nums == null || nums.length < 3) {
			return res;
		}
		sort(nums, 0, nums.length-1);
		
		for (int i=0; i<nums.length-2; i++) {
			
			if (i > 0 && nums[i] == nums[i-1]) {
				continue;
			}
			
			int target = -nums[i];
			
			List<List<Integer>> twoRes = twoSum(nums, i+1, target);
			
			for (List<Integer> list : twoRes) {
				list.add(nums[i]);
				res.add(list);
			}
			
		}
		
		
		return res;
    }
	
	private List<List<Integer>> twoSum(int[] nums, int start, int target) {
		
		List<List<Integer>> res = new ArrayList<>();
		
		int i = start;
		int j = nums.length-1;
		
		while (i < j) {
			
			int sum = nums[i] + nums[j];
			
			if (target == sum) {
				List<Integer> list = new ArrayList<>();
				list.add(nums[i]);
				list.add(nums[j]);
				res.add(list);
				
				while (i < j && nums[i] == nums[i+1]) {
					i++;
				}
				i++;
				while (i < j && nums[j] == nums[j-1]) {
					j--;
				}
				j--;
			} else if (target < sum) {
				j--;
			} else {
				i++;
			}
			
		}
		
		return res;
	}
	
	
	
	private void sort(int[] nums, int lo, int hi) {
		if (lo >= hi) {
			return;
		}
		int povit = partation(nums, lo, hi);
		sort(nums, lo, povit-1);
		sort(nums, povit+1, hi);
	}
	
	private int partation(int[] nums, int lo, int hi) {
		
		int i=lo;
		int j=hi+1;
		
		int v = nums[lo];
		
		while (true) {
			
			while (nums[++i] < v) {
				if (i == hi) {
					break;
				}
			}
			
			while (nums[--j] > v) {
				if (j == lo) {
					break;
				}
			}
			
			if (i >= j) {
				break;
			}
			
			swap(nums, i, j);
			
		}
		
		swap(nums, lo, j);
		
		return j;
		
	}
	
	
	private void swap(int[] nums, int i, int j) {
		int t = nums[i];
		nums[i] = nums[j];
		nums[j] = t;
	}
	
	
	public static void main(String[] args) {
		new Solution015().threeSum(new int[]{-1,0,1,2,-1,-4});
	}
	
}
